package com.desin.modle.datastruct.algo.DynamicAlgorithm.charMatch;

import static sun.swing.MenuItemLayoutHelper.max;

public class Solution1 {
    public int maxNum = Integer.MAX_VALUE;

    public void test(int i,int j,int edit,char[] str,char[] target){
        int strLength = str.length;
        int tarLength = target.length;

        if(i==strLength||j==tarLength){
            if(edit<maxNum){
                maxNum = edit;
            }
            return;
        }
        if(str[i]==target[j]){
            test(i+1,j+1,edit+1,str,target);
        }else{
            test(i+1,j,edit,str,target);
            test(i,j+1,edit,str,target);
        }
    }

    public int test1(char[] str,char[] target){
        int strLength = str.length;
        int tarLength = target.length;

        int[][] states = new int[strLength][tarLength];

        for(int i=0;i<strLength;i++){
            if(str[0]==target[i]){
                states[0][i] = 1;
            }else if(i!=0){
                states[0][i] =states[0][i-1];
            }else{
                states[0][i] =0;
            }
        }

        for(int i=0;i<tarLength;i++){
            if(target[0]==str[i]){
                states[i][0] = 1;
            }else if(i!=0){
                states[i][0] = states[i-1][0];
            }else{
                states[i][0] = 0;
            }
        }

        for(int i=1;i<strLength;i++){
            for(int j=1;j<tarLength;j++){
                if(str[i]==target[j]){
                    states[i][j] = max(states[i-1][j],states[i][j-1],states[i-1][j-1]+1);
                }else{
                    states[i][j] = max(states[i-1][j],states[i][j-1],states[i-1][j-1]);
                }
            }
        }

        return states[strLength-1][tarLength-1];
    }
}
